Skip to main content

A simple proof of a generalized Church-Rosser theorem


Published June 1984
SHOW MORE


Title from cover

"Prepared for: Chief of Naval Research"--Cover

"June 1984"--Cover

"NPS52-84-007"--Cover

Author(s) key words: Church-Rosser, theorem, abstract calculus, tree transformation, term rewriting, functional programming, logic programming, equational programming, production systems, tree, nondeterministic algorithm, normal form, lambda calculus

Includes bibliographical references (p. 13-14)

Technical report; 1984

Abstract calculi (tree transformation systems, term rewriting systems) express computational processes by transformation rules operating on abstract structures (trees). They have applications to functional programming, logic programming, equational programming, productions systems and language processors. We present proof of the Church-Rosser Theorem for a wide, useful class of abstract calculi. This theorem implies that terminating reductions always yield a unique reduced form in these calculi, which has the practical result that transformation rules can be safely applied in any order, or even in parallel. Although this result has previously been established for certain classes of abstract calculi, our proof is much simpler than previous proofs because it is an adaption of Rosser's new (1982) proof of the Church-Rosser Theorem for the lambda calculus

aq/aq cc:9116 02/25/98

kmc/kmc 10/28/09


Publisher Monterey, California : Naval Postgraduate School
Pages 24
Language en_US
Call number ocn460637431
Digitizing sponsor Naval Postgraduate School, Dudley Knox Library
Book contributor Naval Postgraduate School, Dudley Knox Library
Collection navalpostgraduateschoollibrary; fedlink; americana

Full catalog record MARCXML

[Open Library icon]This book has an editable web page on Open Library.

Reviews

There are no reviews yet. Be the first one to write a review.
PEOPLE ALSO FOUND
Source: half
Naval Postgraduate School, Dudley Knox Library
by Williams, Vernon Thomas;Collins, Martin Kevin
54
0
0
Source: half
Naval Postgraduate School, Dudley Knox Library
by Pilcher, Imon Lester.
73
0
0
Source: half
Source: half